#include<iostream>
#include<vector>
#include<list>
#include<queue>
#include<algorithm>
using namespace std;

//大数加法
//class Solution {
//public:
//
//    string solve(string s, string t) {
//        int m = s.size(), n = t.size();
//        int i = m-1, j = n-1, rem = 0;
//
//        string ret;
//        while (i >= 0 || j >= 0)
//        {
//            int left = i >= 0 ? s[i--] - '0' : 0;
//            int right = j >= 0 ? t[j--] - '0':0;
//            rem = rem + left + right;
//            ret += ((rem % 10) + '0');
//            rem /= 10;
//        }
//        if (rem != 0) ret += '1';
//        reverse(ret.begin(), ret.end());
//        cout << ret << endl;
//        return ret;
//    }
//};

//链表相加
//struct ListNode {
//    int val;
//    struct ListNode* next;
//    ListNode(int x) : val(x), next(nullptr) {}
//};
// 
//class Solution {
//public:
//    ListNode* addInList(ListNode* head1, ListNode* head2) {
//        string s1, s2,ret;
//        //将head1和head2的数据存到字符数组中
//        while (head1 != nullptr)
//        {
//            s1 += head1->val;
//            head1 = head1->next;
//        }
//        while (head2 != nullptr)
//        {
//            s2 += head2->val;
//            head2 = head2->next;
//        }
//
//        //将两个数组的值进行相加到另外一个数组ret中
//        int m = s1.size(), n = s2.size();
//        int i = m-1, j = n-1, rem = 0;
//        while (i >= 0 || j >= 0)
//        {
//            int left = i >= 0 ? s1[i--] : 0;
//            int right = j >= 0 ? s2[j--] : 0;
//            rem = rem + left + right;
//            ret += rem % 10;
//            rem /= 10;
//        }
//        //rem可以还存有值
//        if (rem) ret += 1;
//        reverse(ret.begin(), ret.end());
//
//        int size = ret.size();
//        ListNode* head3, * cur,* prev;
//        head3 = cur = new ListNode(ret[0]);
//        for(int i=1; i< size; i++)
//        {
//            prev = cur;
//            cur = new ListNode(ret[i]);
//            prev->next = cur;
//        }
//
//        return head3;
//    }
//};

//大数相乘
//"11"*"99"="1089"
//class Solution {
//public:
//    string Sum(string s, string t) {
//        int m = s.size(), n = t.size();
//        int i = m - 1, j = n - 1, rem = 0;
//
//        string ret;
//        while (i >= 0 || j >= 0)
//        {
//            int left = i >= 0 ? s[i--] - '0' : 0;
//            int right = j >= 0 ? t[j--] - '0' : 0;
//            rem = rem + left + right;
//            ret += ((rem % 10) + '0');
//            rem /= 10;
//        }
//        if (rem != 0) ret += '1';
//        reverse(ret.begin(), ret.end());
//        return ret;
//    }
//
//    //拆分成个位数*多位数
//    string Mul(string s,int n) {
//        int m = s.size();
//        int i = m-1, rem = 0;
//    
//        string ret;
//        while (i >= 0)
//        {
//            int left = s[i--] - '0';
//            rem = rem + left*n;
//            ret += ((rem % 10) + '0');
//            rem /= 10;
//        }
//        if (rem != 0) ret += (rem+'0');
//        reverse(ret.begin(), ret.end());
//        return ret;
//    }
//
//    string solve(string s, string t) {
//        if (t == "0" || s == "0") return "0";
//        int size1 = s.size(), size2 = t.size();
//        string sum;
//        for (int i = size1 - 1; i >= 0; i--)
//        {
//            int n = s[i] - '0';
//            string tmp = Mul(t, n); 
//            for (int j = i; j < size1-1; j++) tmp += '0';//越前面的数,位数要增加
//            sum = Sum(sum, tmp);
//        }
//        cout << sum << endl;
//        return sum;
//    }
//};
//int main()
//{
//    Solution s;
//    //s.Mul("9889", 8);
//    s.solve("101", "9889");
//    return 0;
//}
